#include<iostream>
using namespace std;


void print(int *arr,int n);

void swap(int *left, int *right)
{
    int temp = *left;
    *left = *right;
    *right = temp;
}

void merge(int *arr,int l,int r,int mid)
{
    int lm= l;
    int rm=mid;
    //int *aa = (int *)malloc((r-l+1) * sizeof(int));
    int* aa = new int[r-l];
    int m=0;
    while(lm<mid && rm<r)
        if(arr[lm] < arr[rm])
            aa[m++]= arr[lm++];
        else
            aa[m++] = arr[rm++];
    while(rm<r)
       aa[m++] = arr[rm++];
    while(lm<mid)
        aa[m++] = arr[lm++];
    for (int i=0;i<m;i++)
		arr[l++] = aa[i];
	delete []aa;

}

void mergeSort(int *arr ,int l ,int r)
{
    if(r-l<=1)
       return;
    int mid= (r+l)/2;
    mergeSort(arr,l,mid);
    mergeSort(arr,mid,r);
    merge(arr,l,r, mid);

}


void print(int *arr,int n)
{
    for(int i=0;i<n;i++)
        cout<< arr[i]<<' ' ;
    cout<< endl;

 }

int main()
{
    int a[11] ={2, 8, 4, 5, 9, 4, 42, 0, 3, 6, 8};
    int n=11;
    mergeSort(a,0,n);
    print(a,n);
    return 0;
}


